package Leetcode.每日一题;

import java.util.PriorityQueue;

/**
 * @Author kirito
 * @Date 2023/12/25 10:32
 * @PackageName:Leetcode.每日一题
 * @ClassName: 移除石子使总数最小
 * @Description:
 * 给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：
 *
 * 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。
 * 注意：你可以对 同一堆 石子多次执行此操作。
 *
 * 返回执行 k 次操作后，剩下石子的 最小 总数。
 *
 * floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：piles = [5,4,9], k = 2
 * 输出：12
 * 解释：可能的执行情景如下：
 * - 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
 * - 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
 * 剩下石子的总数为 12 。
 * 示例 2：
 *
 * 输入：piles = [4,3,6,7], k = 3
 * 输出：12
 * 解释：可能的执行情景如下：
 * - 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
 * - 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
 * - 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
 * 剩下石子的总数为 12 。
 *
 * PriorityQueue 是 Java 中的一个队列实现，是一种基于优先级堆（Priority Heap）的数据结构。
 * 它可以用于实现一些基于优先级的算法和应用，例如 Dijkstra 算法、A*算法等等。
 *
 * 在这里，我们创建了一个 PriorityQueue 对象 maxHeap，并传入了一个比较器对象 (a, b) -> b - a 作为参数。
 * 这个比较器用于定义元素之间的优先级，即元素大小的比较方式。
 *
 * (a, b) -> b - a 表示将两个元素 a 和 b 进行比较
 *
 * 如果 a 比 b 大，则返回一个负数
 * 如果 a 比 b 小，则返回一个正数
 * 如果 a 和 b 相等，则返回 0。
 * 这里我们将 b - a 作为返回值，表示我们希望较大的元素在队列中具有较高的优先级，也就是说，我们创建的是一个最大堆。
 * 因此，通过 PriorityQueue 的实现，我们可以很方便地实现一个基于优先级的队列，将元素按照一定的顺序加入队列，
 * 并在取出元素时，始终取出当前队列中优先级最高的元素。

 * @Version 1.0
 */
public class 移除石子使总数最小 {
    //贪心+优先队列
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> integers = new PriorityQueue<>((a, b) -> (b - a));
        for (int pile : piles) {
            integers.offer(pile);
        }
        for (int i = 0; i < k; i++) {
            int p = integers.poll();
            p -= p / 2;
            integers.offer(p);
        }
        int sum = 0;
        while (!integers.isEmpty()) {
            sum += integers.poll();
        }
        return sum;
    }
}
